package leetcode.code0707;

public class MyLinkedList {

	Node head;
	Node tail;

	// 双向链表
	class Node {
		Node prev;
		Node next;
		int val;

		public Node(int _val) {
			val = _val;
		}

		public Node() {

		}
	}

	public MyLinkedList() {
		head = new Node();
		tail = new Node();
		head.next = tail;
		tail.prev = head;
	}

	public int get(int index) {
		Node node = this.getNode(index);
		return node == null ? -1 : node.val;
	}

	public void addAtHead(int val) {
		this.setNode(head, val);
	}

	public void addAtTail(int val) {
		this.setNode(tail.prev, val);
	}

	public void addAtIndex(int index, int val) {
		if (index <= 0) {
			this.addAtHead(val);
			return;
		}
		Node pre = this.getNode(index - 1);
		if (pre != null)
			this.setNode(pre, val);
	}

	public void deleteAtIndex(int index) {
		Node node = this.getNode(index);
		if (node != null) {
			Node pre = node.prev;
			node.next.prev = pre;
			pre.next = node.next;
		}
	}

	// 获得index索引处节点
	private Node getNode(int index) {
		if (index < 0) {
			return head;
		}
		Node find = head.next;
		int idx = 0;
		while (find != tail && idx < index) {
			find = find.next;
			idx++;
		}
		return find == tail ? null : find;
	}

	// pre后添加一个新节点val
	private void setNode(Node pre, int val) {
		Node node = new Node(val);
		node.next = pre.next;
		pre.next.prev = node;
		node.prev = pre;
		pre.next = node;
	}
}
